package com.yeswater.algorithm.leetcode.hot100;

import com.yeswater.algorithm.leetcode.ListNode;

public class Code234 {

    public static void main(String[] args) {
        Code234 code234 = new Code234();
//        ListNode head = new ListNode(new int[]{1, 2, 2, 1});
//        ListNode head = new ListNode(new int[]{1, 2});
        ListNode head = new ListNode(new int[]{1, 2, 3, 2, 1});
        System.out.println(code234.isPalindrome(head));
    }

    /**
     * 我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较
     */
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 快慢指针找到中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 奇数个节点，slow 再走一步
        if (fast != null) {
            slow = slow.next;
        }
        // 反转后半部分链表
        ListNode right = reverse(slow);
        ListNode left = head;
        // 比较回文
        while (right!= null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;

    }

    // 反转,判断相同
    public ListNode reverse(ListNode head) {
        ListNode pre = new ListNode();
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = tmp;
        }
        return pre.next;
    }

}
